package com.algorithms.brownian.pq;

import java.util.Comparator;
import java.util.Iterator;
import java.util.NoSuchElementException;

import com.algorithms.libs.stdlib.io.StdOut;

public final class MinPQ<Key> extends AMaxMinPriorityQueue<Key> {

	protected MinPQ(int capacity) {
		super(capacity);
	}

	public MinPQ() {
		super();
	}

	public MinPQ(int size, Comparator<Key> comparator) {
		super(size, comparator);
	}

	@Override
	protected boolean isHeapValid() {
		return isMinHeap(1);
	}

	private boolean isMinHeap(int k) {
		if (k > size()) {
			return true;
		}
		int left = 2 * k;
		int right = 2 * k + 1;
		if (left <= size() && greater(k, left)) {
			return false;
		}
		if (right <= size() && greater(k, right)) {
			return false;
		}
		return isMinHeap(left) && isMinHeap(right);
	}

	public Key delMin() {

		if (isEmpty()) {
			throw new NoSuchElementException("Priority queue underflow");
		}

		Key key = getValueAtPosition(1);
		exch(1, decreaseSize());
		sink(1);
		setValuAtPos(size() + 1, null);
		checkSize();
		return key;
	}

	@Override
	public Iterator<Key> iterator() {
		return new HeapIterator();
	}

	public Key min() {
		if (isEmpty()) {
			throw new NoSuchElementException("Priority queue underflow");
		}
		return getValueAtPosition(1);
	}

	@Override
	protected void swim(int k) {
		while (k > 1 && greater(k / 2, k)) {
			exch(k, k / 2);
			k = k / 2;
		}

	}

	@Override
	protected void sink(int k) {
		while (2 * k <= size()) {
			int j = 2 * k;
			if (j < size() && greater(j, j + 1)) {
				j++;
			}
			if (!greater(k, j)) {
				break;
			}
			exch(k, j);
			k = j;
		}

	}

	protected final class HeapIterator extends AHeapterator {

		@Override
		protected AMaxMinPriorityQueue<Key> createHeap() {
			return new MinPQ<Key>(size());
		}

		@Override
		protected AMaxMinPriorityQueue<Key> createHeap(
				Comparator<Key> comparator) {
			return new MinPQ<>(size(), comparator);
		}

		public Key next() {
			if (!hasNext())
				throw new NoSuchElementException();
			return delete();
		}
	}

	@Override
	public Key delete() {
		return delMin();
	}

	/**
	 * Unit tests the <tt>MaxPQ</tt> data type.
	 */
	public static void main(String[] args) {
		MinPQ<Integer> pq = new MinPQ<Integer>();
		pq.insert(0);
		pq.insert(1);
		pq.insert(27);
		pq.insert(8);
		pq.insert(4);
		pq.insert(3);
		while (!pq.isEmpty())
			StdOut.println(pq.delMin());
	}

}
